package LeetCode;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName interview
 * @Description: TODO
 * @date ${DAT}9:42
 */
public class DP01 {
    public static void main(String[] args) {
        int[] arr = {1,2,4,1,7,8,3};
        System.out.println(rec_opt(arr, arr.length - 1));
        System.out.println(dp_opt(arr));
    }

    /**
     * 递归版本
     * @param arr
     * @param index OPT(i)的下标
     */
    public static int rec_opt(int[] arr,int index){
        if (index == 0){
            return arr[0];
        }
        if (index == 1){
            return Math.max(arr[0],arr[1]);
        }
        return Math.max(rec_opt(arr,index - 2) + arr[index],rec_opt(arr,index - 1));
    }

    /**
     * 动态规划转移方程的形式
     * @param arr
     * @return
     */
    public static int dp_opt(int[] arr){
        int[] dp = new int[arr.length];
        dp[0] = arr[0];
        dp[1] = Math.max(arr[0],arr[1]);
        for (int i = 2; i < arr.length; i++){
            dp[i] = Math.max(dp[i - 2]+arr[i],dp[i - 1]);
        }
        return dp[dp.length -1];
    }
}
